package Review;

import java.lang.reflect.Array;
import java.util.Arrays;

/*建立大根堆：从最后一颗子树的根节点开始进行调整，在数组本身上进行调整*/
/*大根堆：如果根节点比左右孩子都大，就是大根堆
* 小根堆：入宫根节点比左右孩子都小，此时就是小根堆
* 左右孩子之间没有大小关系*/
/*堆的存储：用数组，堆就是一颗完全二叉树，如果不是一颗完全二叉树，会造成数组空间的浪费
* 如果是建立小根堆，此时只需要改变大于号和小于号即可*/
/*向上调整：在大根堆进行插入元素的时候然后要重新调整为大根堆，插入的元素是放在数组的最后，
* 此时的调整就是向上调整，从最后一个节点开始进行比较*/
/*向下调整：是在建堆的时候是从每颗子树进行向下调整，指的是每颗子树从根向下调整*/
/*建堆的时候也是可以使用向上调整的，不是只有在插入元素的时候才能使用向上调整*/
/**/
public class TextHeap {
    public int[] elem;
    public int useSized;
    public static final int DEFAULT_SIZE = 10;

    public TextHeap() {
        elem = new int[DEFAULT_SIZE];
    }

    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            useSized++;
        }
    }
    /*建堆的时间复杂度：O（n）（用到错位相减法和求节点个数的公式来推导的）*/
    public void createHeap() {
        //从最后一个子树的根节点开始进行调整
        /*(useSized-2)/2一直孩子节点，推导父亲节点，0下标这棵树也需要进行调整
        * parent--是因为从最后一个子树的根节点的下标开始往前走*/
        for (int parent = (useSized-2)/2; parent >= 0; parent--) {
            /*这里第二个参数是usedSize是因为每次调整之后程序如何才能知道此时调整
            * 应该结束了，当定义的孩子下标往下走的时候，发现下标值超过了usedSize
            * 此时就说明没有这个孩子节点，此时调整结束*/
            shiftDown(parent,useSized);//从每颗子树向下调整
        }
    }
    /*parent:每棵树的根节点
    * len：每颗子树调整的结束位置  不能大于len（这里的参数传过来的是usedSize）*/
    private void shiftDown(int parent, int len) {
        int child = 2*parent + 1;
        //1.必须保证有左孩子
        while (child < len) {
            //child+1 < len是为了必须保证有右孩子
            if (child+1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            if (elem[parent] < elem[child]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                //此时只能保证局部是大根堆，但是整体还没有调整结束
                parent = child;
                child = parent*2 + 1;//child继续是parent的左孩子
            }else {
                break;//说明此时已经是大根堆
            }
        }
    }
    //插入元素    时间复杂度：O(logN) 最大调整树的高度
    public void offer(int val) {
        if (isFull()) {
            //2倍扩容
            elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[useSized] = val;
        useSized++;
        //然后想办法重新调整为大根堆
        shiftUp(useSized - 1);//这里参数传的是下标
    }
    private void shiftUp(int child) {
        int parent = (child - 1) / 2;
        while (child > 0) {//此时0下标的位置也是需要调整的
            //但是此时不能是parent > 0，parent为0的时候还没有调整0下标位置的节点
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] =  elem[parent];
                elem[parent] = tmp;
                //此时还是只是局部是大根堆
                child = parent;
                parent = (child-1) / 2;
            }else {
                break;
            }
        }
    }
    private boolean isFull() {
        return useSized == elem.length;
    }
    //删除堆中的元素（一定只能删除堆顶元素）
    public int pop () {
        if (isEmpty()) return -1;
        //交换堆顶和最后一个位置的元素
        int tmp = elem[0];
        elem[0] = elem[useSized - 1];
        elem[useSized - 1] = tmp;
        useSized--;
        //保证它仍然是一个大根堆
        shiftDown(0,useSized);
        return tmp;//tmp就是删除的元素
    }

    public boolean isEmpty() {
        return useSized == 0;
    }
    //查看堆顶元素
    public int peek() {
        if (isFull()) return -1;
        return elem[0];
    }
}
